class Solution(object):
    def shortestBridge(self, grid):
        m = len(grid)
        n = len(grid[0])
        edge_set = set()
        flag = False
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    now_set = {(i, j)}
                    search_set = {(i, j)}
                    while now_set:
                        next_set = set()
                        for x, y in now_set:
                            for ux, uy in [(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)]:
                                if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in search_set:
                                    if grid[ux][uy]:
                                        next_set.add((ux, uy))
                                    else:
                                        edge_set.add((ux, uy))
                                    search_set.add((ux, uy))
                        now_set = next_set
                    flag = True
                    break
            if flag:
                break
        dist = 1
        while edge_set:
            next_set = set()
            for x, y in edge_set:
                for ux, uy in [(x + 1, y), (x - 1, y), (x, y - 1), (x, y + 1)]:
                    if 0 <= ux < m and 0 <= uy < n and (ux, uy) not in search_set:
                        if grid[ux][uy]:
                            return dist
                        else:
                            next_set.add((ux, uy))
            edge_set = next_set
            dist += 1
        return dist


data = Solution()
grid = [[0, 1, 0], [0, 0, 0], [0, 0, 1]]
print(data.shortestBridge(grid))
